package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.TreeSet;

/**
 * 958. 二叉树的完全性检验
 * @author feizns
 * @since 2020/3/14
 */
public class IsCompleteTree {

    public static void main(String[] args) {

        TreeSet<Integer> a = new TreeSet<>();
        a.add(1);
        System.out.println(a.pollLast());
        System.out.println(a);

//        System.out.println(isCompleteTree(create()));

    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.left.left = new TreeNode(5);
        ret.right = new TreeNode(3);
        ret.right.left = new TreeNode(7);
        return ret;
    }

    static TreeSet<Integer> set = new TreeSet<>();

    public static boolean isCompleteTree(TreeNode root) {
        dfs(root, 0);
        Integer val = set.last();
        if ( val != null ) {
            int i = 0;
            for(int a : set) {
                if (a != i++)
                    return false;
            }
//            for (int i = 0; i < val; i++) {
//                if ( !set.contains(i) )
//                    return false;
//            }
        }
        return true;
    }

    private static void dfs(TreeNode root, int v) {
        if ( root != null ) {
            System.out.println(root.val);
            set.add(v);
            dfs(root.left, 2 * v + 1);
            dfs(root.right, 2 * v + 2);
        }
    }

}
